/*
 * shinglehashtable.cpp
 *
 *  Created on: Jun 6, 2011
 *      Author: timothy
 */

#include "shinglehashtable.h"
#include "init.h"
#include "debug.h"
#include "list.h"

extern arg_vars *g_ArgVars;

ShingleHashtableEntry** allocatedSHTEntries;
int* numSHTAllocations;

ShingleHashtable::ShingleHashtable(int vertices)
{
	Size = vertices * g_ArgVars->num_trials;
	if(Size < 1024) Size = 1024;
	count = 0;
	write_locks = (omp_lock_t*)calloc(Size, sizeof(omp_lock_t));
	for(unsigned long i = 0; i < Size; ++i)
		omp_init_lock(&write_locks[i]);
	omp_init_lock(&table_lock);
	table = (ShingleHashtableEntry**)calloc(Size, sizeof(ShingleHashtableEntry*));
	if(!table)
	{
		pdprint(PDPRINT_ALL, "Insufficient memory for table.\n");
		exit(1);
	}
	for(unsigned long i = 0; i < Size; ++i)
		table[i] = NULL;
	tableBackup = table;
//	pdprint(PDPRINT_HASH, "Table initialized: checking...\n");
	mostRecentEntries = (ShingleHashtableEntry**)calloc(omp_get_max_threads(), sizeof(ShingleHashtableEntry*));
	iterators = (ShingleHashtableEntry**)calloc(omp_get_max_threads(), sizeof(ShingleHashtableEntry*));
	firstEntry = (ShingleHashtableEntry**)calloc(omp_get_max_threads(), sizeof(ShingleHashtableEntry*));
#pragma omp parallel
	{
		int i = omp_get_thread_num();
		mostRecentEntries[i] = NULL;
		iterators[i] = NULL;
		firstEntry[i] = NULL;
		insTimes[i] = 0;
		lstTimes[i] = 0;
		genTimes[i] = 0;
		chkTimes[i] = 0;

		lockedTimes[i] = 0;
		lockingTimes[i] = 0;
		lastLock[i] = 0;
		collisions[i] = 0;
		timesLocked[i] = 0;
	}
}
ShingleHashtable::~ShingleHashtable()
{
	for(unsigned long i = 0; i < Size; ++i)
		omp_destroy_lock(&write_locks[i]);
#ifndef SINGLE_ITERATOR
	for(int i = 0; i < omp_get_max_threads(); ++i)
		mostRecentEntries[i]->ClearData();
#else // SINGLE ITERATOR
	mostRecentEntries[0]->ClearData();
#endif
	free(firstEntry);
	free(mostRecentEntries);
	free(iterators);
	free(write_locks);
	free(table);
}

// Adds the shingle GENERATED BY item to the hashtable
// In the case of duplicate shingles, this will merely add extra links to the existing one.
// In the case of an actual collision, this will use ShingleHashtableEntry->Next
// This method uses locks to stay threadsafe.
void ShingleHashtable::Insert(Vertex *item, int nthShingle)
{
	if(item->Neighbors->Size() < g_ShingleContext->s)
		return;
	//pdprint(PDPRINT_SHINGLE_2, "Creating shingle %d for vertex %d\n", nthShingle, item->ID);

#ifdef IGNORE_SMALL_TIMES
	unsigned long key = Shingle::MakeKey(item, nthShingle);
	Shingle *fetch = Fetch(key, nthShingle);
	if(fetch)
	{
		lock(indexOf(key));
//		fetch->VerifyNeighbor(item);
		fetch->Neighbors->Push(item->ID);
		fetch->neighborCount++;
		unlock(indexOf(key));
		return;
	}
	Shingle *ins = item->MakeShingle(nthShingle, 0);

	if(ins)
		InnerInsert(ins);
#else // NO IGNORE_TIMING_DATA
	double t1, t2, t3, t0;

	int proc = omp_get_thread_num();
	t0 = omp_get_wtime();
	unsigned long key = Shingle::MakeKey(item, nthShingle);
	Shingle *fetch = Fetch(key, nthShingle);
	t1 = omp_get_wtime();
	double chkTime = t1 - t0;
	chkTimes[proc] += chkTime;
	if(fetch)
	{
		t2 = omp_get_wtime();
		lock(indexOf(key));
//		fetch->VerifyNeighbor(item);
		fetch->Neighbors->Push(item->ID);
		fetch->neighborCount++;
		unlock(indexOf(key));
		t3 = omp_get_wtime();
		lstTimes[proc] += t3 - t2;
		return;
	}
	Shingle *ins = item->MakeShingle(nthShingle, 0);
	t2 = omp_get_wtime();

	if(ins)
		InnerInsert(ins);
	t3 = omp_get_wtime();

	double genTime = t2 - t1;
	double insTime = t3 - t2;
	insTimes[proc] += insTime;
	genTimes[proc] += genTime;
#endif // NO IGNORE_TIMING_DATA
}
void ShingleHashtable::Insert(Shingle *item, int nthShingle)
{
//	if(item->neighborCount < g_ArgVars->shingle_length)
//		return;
	//pdprint(PDPRINT_SHINGLE_2, "Creating shingle %d for shingle %ld\n", nthShingle, item->hashkey);

	unsigned long key = Shingle::MakeKey(item, nthShingle);
	Shingle *fetch = Fetch(key, nthShingle);
	if(fetch)
	{
		fetch->Neighbors->Push(item->hashkey);
		fetch->neighborCount++;
		return;
	}
	Shingle *ins = item->MakeShingle(nthShingle, key);
	if(ins)
		InnerInsert(ins);
}

// Finds a shingle in the hashtable
// This method is threadsafe with itself, but not with Insert.
// Returns NULL if no value exists at the given key.
Shingle* ShingleHashtable::Fetch(unsigned long key, int nthShingle)
{
	ShingleHashtableEntry *ret = check(key, nthShingle);
	if(ret)
		return ret->Item;
	else
		return NULL;
}

// Gets the current number of items
int ShingleHashtable::Count()
{
	return count;
}

// Functions for iterating through the hashtable.
void ShingleHashtable::InitIterator()
{
#ifndef SINGLE_ITERATOR
	for(int i = 0; i < omp_get_max_threads(); ++i)
	{
		iterators[i] = mostRecentEntries[i];
	}
#endif
#ifdef SINGLE_ITERATOR
	for(int i = 1; i < omp_get_max_threads(); ++i)
	{
		if(firstEntry[i-1] != NULL)
			if(mostRecentEntries[i] != NULL)
			firstEntry[i-1]->ListNext = (mostRecentEntries[i]);
	}
	iterators[omp_get_thread_num()]=mostRecentEntries[omp_get_thread_num()];
#endif
}
Shingle* ShingleHashtable::Iterate()
{
	Shingle *ret = NULL;
#ifndef SINGLE_ITERATOR
	int thread = omp_get_thread_num();
	{
		if(!iterators[thread]) ret = NULL;
		else
		{
			ret =iterators[thread]->Item;
			iterators[thread]=iterators[thread]->ListNext;
		}
	}
#else
#ifndef PARALLEL_ON_TRIALS
#pragma omp critical // omp critical unless parallel on trials
#endif
	{
		ShingleHashtableEntry *it = iterators[0];
		if(it)
		{
				ret = it->Item;
				iterators[0] = it->ListNext;
		}
	}
#endif
	return ret;
}

// PRIVATE HELPER METHODS //
ShingleHashtableEntry* ShingleHashtable::check(long unsigned int key, int nthShingle)
{
	// This method is neither threadsafe nor critical. Users are expected to be thread-careful.
	// pdprint(PDPRINT_HASH, "Looked up %ld to %ld\n", key, indexOf(key));
	ShingleHashtableEntry *ret = table[indexOf(key)];
	while(ret)
	{
		if(ret->Item->hashkey == key && ret->Item->nthShingle == nthShingle)
			return ret;
		ret = ret->GetNext();
	}
	return NULL;
}
long unsigned int ShingleHashtable::indexOf(long unsigned int key)
{
	return key%Size;
}
unsigned long int ShingleHashtable::getKey(Shingle *s)
{
	return s->hashkey;
}
void ShingleHashtable::InnerInsert(Shingle *ins)
{
	unsigned long key = ins->hashkey;
	int nthShingle = ins->nthShingle;
	Shingle *fetch = Fetch(key, nthShingle);
	unsigned long index = indexOf(getKey(ins));
	ShingleHashtableEntry *entry = table[index];
	if(!fetch)
	{
		ShingleHashtableEntry *make = ShingleHashtableEntry::AllocateShingleHashtableEntry(ins);
		make->SetNext(table[index]);
#ifndef ACCUMULATE_SHINGLES
		lock(index);
		if(table[index] == entry)
		{
			table[index] = make;
			++count;
			unlock(index);
		}
		else
		{
			// This can happen if another thread writes over table[index] before we lock.
			fetch = Fetch(getKey(ins), nthShingle);
			if(fetch)
			{
				unlock(index);
//				pdprint(PDPRINT_THREADING, "Overwritten at beginning of list.\n");
				make->Item = 0;
				make->ListNext = 0;
				make->SetNext(0);
				ShingleHashtableEntry::Deallocate();
				goto found_entry; // Yes, yes, I know, but it's better than using recursion or a loop.
			}
			make->SetNext(table[index]);
			table[index] = make;
			++count;
			unlock(index);
		}
#pragma omp flush
#else
		make->SetNext(table[index]);
		table[index] = make;
		++count;
#endif
		make->ListNext = mostRecentEntries[omp_get_thread_num()];
		if(firstEntry[omp_get_thread_num()] == 0)
			firstEntry[omp_get_thread_num()] = make;
		mostRecentEntries[omp_get_thread_num()] = make;

		return;
	}
	else
	{
		found_entry:

		unsigned long Item = ins->Neighbors->Head();
		lock(indexOf(key));
		++fetch->neighborCount;
		fetch->Neighbors->Push(Item);
		unlock(indexOf(key));
#pragma omp flush

#ifdef BULK_ALLOCATE_SHINGLES
#ifndef ACCUMULATE_SHINGLES // Cannot Deallocate shingles that were not the most recently allocated
		Shingle::DeallocateShingle();
#endif // ACCUMULATE SHINGLES
#else // BULK_ALLOCATE_SHINGLES
		delete(ins);
#endif // BULK_ALLOCATE_SHINGLES
		return;
	}
}
void ShingleHashtable::lock(unsigned long index)
{
#ifdef IGNORE_SMALL_TIMES
	omp_set_lock(&write_locks[index]);
#else // NO IGNORE_SMALL_TIMES
	int proc = omp_get_thread_num();
	double start = omp_get_wtime();
	if(!omp_test_lock(&write_locks[index]))
	{
		collisions[proc]++;
		omp_set_lock(&write_locks[index]);
	}
	lockingTimes[proc] += omp_get_wtime() - start;
	lastLock[proc] = omp_get_wtime();
	++timesLocked[proc];
#endif // NO IGNORE_SMALL_TIMES
}
void ShingleHashtable::unlock(unsigned long index)
{
#ifdef IGNORE_SMALL_TIMES
	omp_unset_lock(&write_locks[index]);
#else // NO IGNORE_SMALL_TIMES
	omp_unset_lock(&write_locks[index]);
	int proc = omp_get_thread_num();
	lockedTimes[proc] += omp_get_wtime() - lastLock[proc];
#endif // NO IGNORE_SMALL_TIMES
}

// SHINGLEHASHTABLEENTRY CONSTRUCTOR //
ShingleHashtableEntry *ShingleHashtableEntry::AllocateShingleHashtableEntry(Shingle *item)
{
#ifndef BULK_ALLOCATE_SHINGLES
	return new ShingleHashtableEntry(item);
#else // BULK_ALLOCATE_SHINGLES
	int proc = omp_get_thread_num();
	if(numSHTAllocations[proc] == 0)
	{
		numSHTAllocations[proc] = BULK_ALLOCATE_SHINGLES;
		allocatedSHTEntries[proc] = (ShingleHashtableEntry*)calloc(BULK_ALLOCATE_SHINGLES, sizeof(ShingleHashtableEntry));
	}
	int index = BULK_ALLOCATE_SHINGLES - numSHTAllocations[proc]--;

	ShingleHashtableEntry *ret = &allocatedSHTEntries[proc][index];

	ret->Finished = 0;
	ret->Next = 0;
	ret->Item = item;
	ret->ListNext = NULL;
	if(ret->Item->isMemoryBlock)
		ret->hasMemoryBlock = 1;
	else
		ret->hasMemoryBlock = 0;
	ret->neighborCount = 0;
	if(index == 0)
	{
		ret->parent = NULL;
		ret->neighborCount = BULK_ALLOCATE_SHINGLES;
	}
	else
		ret->parent = &allocatedSHTEntries[proc][0];

	return ret;
#endif // BULK_ALLOCATE_SHINGLES
}
void ShingleHashtableEntry::Deallocate()
{
	numSHTAllocations[omp_get_thread_num()]++;
}

void ShingleHashtableEntry::SetupAllocs()
{
	int maxThreads = omp_get_max_threads();
	allocatedSHTEntries = (ShingleHashtableEntry**)calloc(maxThreads, sizeof(ShingleHashtableEntry*));
	numSHTAllocations = (int*)calloc(maxThreads, sizeof(int));
	for(int i = 0; i < maxThreads; ++i)
	{
		allocatedSHTEntries[i] = 0;
		numSHTAllocations[i] = 0;
	}
}
ShingleHashtableEntry::ShingleHashtableEntry(Shingle *item)
{
	if(item == NULL) pdprint(PDPRINT_ALL, "Created hash-entry with no item.\n");
	Finished = 0;
	Next = 0;
	Item = item;
	ListNext = NULL;
	if(item->isMemoryBlock)
		this->hasMemoryBlock = 1;
	else
		this->hasMemoryBlock = 0;
}
ShingleHashtableEntry::~ShingleHashtableEntry()
{

}
void ShingleHashtableEntry::ClearData()
{
	if(Item)
	{
		Item->ClearData();
		Item = 0;
	}
	while(ListNext)
	{
		ShingleHashtableEntry *del = ListNext;
		ListNext = del->ListNext;
		del->ListNext = 0;
		del->ClearData();
	}
	if(parent)
	{
		parent->neighborCount--;
		if(parent->neighborCount == 0)
			free(parent);
	}
	else
	{
		neighborCount--;
		if(neighborCount == 0)
			free(this);
	}
}

void ShingleHashtableEntry::SetNext(ShingleHashtableEntry *to)
{
	Next = to;
}
ShingleHashtableEntry *ShingleHashtableEntry::GetNext()
{
	return Next;
}
